package com.leetcode.algorithm.y19.m03;

import java.util.Stack;

import com.leetcode.algorithm.common.TreeNode;

/**
 * 449. 序列化和反序列化二叉搜索树
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 * 
 * 序列化是将数据结构或对象转换为一系列位的过程，以便它可以存储在文件或内存缓冲区中，或通过网络连接链路传输，以便稍后在同一个或另一个计算机环境中重建。
 * 
 * 设计一个算法来序列化和反序列化二叉搜索树。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。
 * 
 * 编码的字符串应尽可能紧凑。
 * 
 * 注意：不要使用类成员/全局/静态变量来存储状态。 你的序列化和反序列化算法应该是无状态的。
 */
public class BinarySearchTreeCodec {

    // Encodes a tree to a single string.
	public String serialize(TreeNode root) {
		// 思路:
		// 二叉搜索树可以通过前序或者后序遍历编码，以下实现通过前序遍历编码
		StringBuilder str = new StringBuilder();
		if (root == null) {
			return "";
		}
		Stack<TreeNode> stack = new Stack<TreeNode>();
		stack.push(root);
		while (!stack.isEmpty()) {
			TreeNode node = stack.pop();
			if (str.length() > 0) {
				str.append(",");
			}
			str.append(node.val); // 遍历当前结点
			if (node.right != null) { // 入栈顺序为先右孩子后左孩子，以确保出栈时的顺序是先左后右
				stack.push(node.right);
			}
			if (node.left != null) {
				stack.push(node.left);
			}
		}
		return str.toString();
	}

    // Decodes your encoded data to tree.
	public TreeNode deserialize(String data) {
		if ("".equals(data)) {
			return null;
		}
		String[] arrs = data.split(",");
		int[] nums = new int[arrs.length];
		for (int i = 0; i < nums.length; i++) {
			nums[i] = Integer.parseInt(arrs[i]);
		}
		return bstFromPreorder(nums, 0, nums.length);
	}

	private TreeNode bstFromPreorder(int[] preorder, int fromIdx, int toIdx) {
		if (fromIdx >= toIdx) {
			return null;
		}
		TreeNode root = new TreeNode(preorder[fromIdx]);
		int i = fromIdx + 1;
		for (; i < toIdx; i++) {
			if (preorder[i] >= preorder[fromIdx]) {
				break;
			}
		}
		root.left = bstFromPreorder(preorder, fromIdx + 1, i);
		root.right = bstFromPreorder(preorder, i, toIdx);
		return root;
	}
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));